package com.simon.study.algorithm.tree;

import lombok.NoArgsConstructor;

/**
 * <p>
 *
 * @author simon
 * @date 2022/8/21 4:52 下午
 */
@NoArgsConstructor
public class Tree1 extends Tree{
    TNode root;

    public Tree1(TNode root) {
        this.root = root;
    }


    public TNode add(int k){
        TNode parent = findParent(k);
        return create(k, parent);
    }

    public TNode findParent(int k){
        TNode node = root, pre = null;

        while (node != null){
            pre = node;
            if( k > node.data ){ node = node.right; }
            else{ node = node.left; }
        }

        return pre;
    }


    public TNode find(int k){
        TNode node = root;

        while (node != null){
            if( k > node.data ){ node = node.right; }
            else if( k == node.data ){ return node; }
            else{ node = node.left; }
        }

        return null;
    }

    private TNode create(int data, TNode parent){
        TNode node  = new TNode(data);
        node.parent = parent;
        if(parent == null){ root = node; }
        else {
            if( data > parent.data ){
                parent.right = node;
            }else{
                parent.left  = node;
            }
        }

        return node;
    }


    public static void main(String[] args) {
        int[] arr = {2, 8, 10, 23, 1, 7, 12, 18, 5, 6};
        Tree1 nt = new Tree1();
        for (int i = 0; i < arr.length; i++) {
            nt.add(arr[i]);
        }
        nt.hiarachicallyPrint();

        Tree1 tree = new Tree1(createMaxHeapTree(arr));
        tree.hiarachicallyPrint();
    }


    public TNode leftRotate(TNode spot){
        TNode node = super.leftRotate(spot);

        // adjust parent
        node.parent    = spot.parent;
        spot.parent    = node;
        if(spot.right != null) {
            spot.right.parent = spot;
        }

        // adjust left/right for parent
        // adjust root
        if(node.parent != null){
            if( node.data < node.parent.data ){ node.parent.left = node; }
            else{ node.parent.right = node; }
        }else{ root = node; }
        return node;
    }

    public TNode rightRotate(TNode spot){
        TNode node = super.rightRotate(spot);

        // adjust parent
        node.parent   = spot.parent;
        spot.parent = node;

        if(spot.left != null) {
            spot.left.parent = spot;
        }

        if(node.parent != null){
            if( node.data < node.parent.data ){ node.parent.left = node; }
            else{ node.parent.right = node; }
        }else{ root = node; }

        return node;
    }
}

